#include <stdio.h>
#include <stdlib.h>

#define MAX 10
typedef char DataType;

// 二叉树
typedef struct node {
    DataType data;
    struct node *left, *right;
} LinkTree;

// 栈
typedef struct {
    LinkTree *list[MAX];
    int top;
} Stack;

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int isFull(Stack *stack) {
    return stack->top == MAX - 1;
}

void push(Stack *stack, LinkTree *value) {

    if (isFull(stack)) {
        printf("stack is full! top={%d}\n", stack->top);
        return;
    }
    stack->list[++stack->top] = value;
}

/**
 * 获取栈顶元素，但是不退栈
 * @return
 */
LinkTree *get(Stack *stack) {

    if (isEmpty(stack)) {
        printf("stack is empty!\n");
        return NULL;
    }
    return stack->list[stack->top];
}


LinkTree *pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("stack is empty!\n");
        return NULL;
    }
    return stack->list[stack->top--];
}

Stack *initStack() {

    Stack *stack = (Stack *) malloc(sizeof(Stack));
    stack->top = -1;

    return stack;
}

LinkTree *init() {

    DataType ch;

    // 头元素
    LinkTree *top = NULL;
    // 新元素
    LinkTree *item = NULL;

    int k;

    Stack *stack = initStack();

    while ((ch = getchar()) != '\n') {

        switch (ch) {

            case '(':
                push(stack, top);
                k = 1;
                break;
            case ',':
                k = 2;
                break;
            case ')':
                top = pop(stack);
                break;
            default:
                item = (LinkTree *) malloc(sizeof(LinkTree));
                item->data = ch;
                item->left = NULL;
                item->right = NULL;

                top = item;

                LinkTree *d = get(stack);

                if (d != NULL) {
                    if (k == 1) {
                        // 操作左侧
                        d->left = item;
                    } else {
                        // 操作右侧
                        d->right = item;
                    }
                }
                break;
        }

    }

    return top;
}

void printNode(LinkTree *tree) {
    printf("%c,", tree->data);
}

// 先序遍历
void first(LinkTree *tree) {
    if (NULL == tree) {
        return;
    }
    printNode(tree);
    first(tree->left);
    first(tree->right);
}

//　中序遍历
void second(LinkTree *tree) {
    if (NULL == tree) {
        return;
    }
    second(tree->left);
    printNode(tree);
    second(tree->right);
}

// 后序遍历
void last(LinkTree *tree) {
    if (NULL == tree) {
        return;
    }

    last(tree->left);
    last(tree->right);
    printNode(tree);
}

// 非递归，中序遍历
void preOrderEach(LinkTree *tree) {

    Stack *stack = initStack();
    push(stack, tree);

    while (!isEmpty(stack)) {

        LinkTree *item = pop(stack);
        if (item != NULL) {
            printNode(item);
            push(stack, item->right);
            push(stack, item->left);
        }
    }

}


int main() {
    printf("Please input:D(A,B) \n");

    LinkTree *linkTree = init();
    printf("top data=%c\n", linkTree->data);
    printf("top left data=%c\n", linkTree->left->data);
    printf("top right data=%c\n", linkTree->right->data);

    printf("first each... \n");
    first(linkTree);
    printf("\n");

    printf("second each... \n");
    second(linkTree);
    printf("\n");

    printf("last each... \n");
    last(linkTree);
    printf("\n");

    // 非递归方式的遍历
    preOrderEach(linkTree);

    return 0;
}
